package 堆排序01;

import java.util.Arrays;

/**
 * Created by hest0 on 2017/5/4.
 */
public class 堆排序 {
    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        HeapSort hs = new HeapSort();
        hs.heapSort(a);
        System.out.println("排序后的数组是：");
        System.out.println(Arrays.toString(a));
    }

}

class HeapSort {
    void heapSort(int[] a) {
        // 循环建立初始堆,若父节点索引为i，那么左节点的索引为i*2+1，即左节点为a.length时，其父节点应当小于a.length/2
        // 遍历存在子节点的父节点
        for (int i = a.length / 2; i >= 0; i--)
            adjustHeap(a, i, a.length - 1);

        // 进行n-1次循环完成排序
        for (int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i);
            adjustHeap(a, 0, i);
        }
    }

    /**
     * a是堆，p是父节点下标，s左子节点下标
     * 将数组转换为大根堆，大根堆的根节点为数组中的最大值
     *
     * @param a
     * @param p
     * @param len
     */
    private void adjustHeap(int[] a, int p, int len) {
        int tmp = a[p];
        int ls = 2 * p + 1;
        //判断左节点是不是大于最大索引
        while (ls < len) {
            //右孩子>左孩子，下标取右孩子
            ls = ls + 1 < len && a[ls] < a[ls + 1] ? ls + 1 : ls;
            // 当父节点的值直接大于子节点的值时，直接退出
            if (tmp > a[ls]) break;
            // 将子节点的值赋值给父节点
            a[p] = a[ls];
            // 选取子节点的左子节点作为父节点继续向下筛选
            p = ls;
            ls = 2 * p + 1;
        }
        a[p] = tmp;
    }

    //交换数组2个元素
    private void swap(int[] a, int i, int j) {
        a[i] = a[i] ^ a[j];
        a[j] = a[i] ^ a[j];
        a[i] = a[i] ^ a[j];
    }

}
